package algorithm.backtracing;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 90. Subsets II
 * leetcode : https://leetcode.com/problems/subsets-ii/
 * Difficutly : Medium
 *
 * 给一个含有重复元素的数组 num。求所有可能的子集合，要求子集合去重
 * Example
 * Input:[1,2,2]
 * Output:[
 *  [],
 *  [1],
 *  [2],
 *  [1,2],
 *  [2,2],
 *  [1,2,2]
 * ]
 *
 * @Author Antony
 * @Since 2018/11/16 16:12
 */
public class SubSetsII {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,2};
        int[] arr_2 = new int[]{4,4,4,1,4};
        System.out.println(GsonUtil.toJson(subsetsWithDup(arr)));
        System.out.println(GsonUtil.toJson(subsetsWithDup(arr_2)));
    }

    /**
     * leetcode : 2ms - beats 100.0%
     *
     * 对SubSets BFS 算法的改进版
     * 也是对于每一个读到的元素，我们选择把他追加到已生成结果的集合里。
     * 以此来构建新的集合，并且添加到result中
     *
     * 区别在于，我们要对子集合结果去重，那么优化是：
     * 1）首先要对nums排序，使用Arrays.sort() 函数，从小到大有序
     * 2）当我们遍历时，遇到当前值==上一个值 （也就是 i>=1 && n == nums[i-1) ）
     *  那么如果这个值还按原有方法，从已有集合的0到末尾来往里添加，那就必然会有重复的结果存在。
     * 3）通过分析可以知道，重复的结果，是在上一个元素往里添加前，集合中已存在的元素。这些元素再组合会重复。
     *
     * 这里举栗可以看出：
     * 第一层: 空 = []
     * 第二层：1  = [[],[1]]
     * 第三层：2  = [[],[1],[2],[1,2]]
     * 第四层：2  此时要从上一个开始时的尾index开始，跳过已经添加过的 [],[1] 也就是组合 [2],[1,2]
     *          那么结果就是 [[],[1],[2],[1,2],[2,2],[1,2,2]]
     *
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        int beforeAddSize = 0;
        for(int i=0; i<nums.length; i++){
            int n = nums[i];
            int startIdx = 0;
            if(i>=1 && n==nums[i-1]){
                startIdx = beforeAddSize;
            }
            int currSize = result.size();
            beforeAddSize = result.size();

            for(;startIdx<currSize; startIdx++){
                List<Integer> subSet = new ArrayList<>(result.get(startIdx));
                subSet.add(n);
                result.add(subSet);
            }
        }
        return result;
    }

}
